package Tree;

import java.util.Stack;

public class BinaryTreeCreate {

	/**
	 * 用来表示根节点
	 */
	public TreeNode root = null; // 首先，根节点为null

	public static void main(String[] args) {

		int a[] = { 1, 5, 21, 27, 36, 59, 42 };
		BinaryTreeCreate tree = new BinaryTreeCreate();
		for (int i = 0; i < a.length; i++) {
			tree.createBinaryTree(tree.root, a[i]);
		}
		preOrder(tree.root);
		System.out.println("");
		inOrder(tree.root);
		System.out.println("");
		postOrder(tree.root);
	}

	// 创建二叉树
	// 注意，循环调用该函数的是root结点，即每次从root节点下开始。
	public void createBinaryTree(TreeNode node, int value) {
		// 如果根节点为空的话，就创建根节点
		if (root == null) {
			root = new TreeNode(value);
		} else {
//			Random random = new Random();
//			int i = random.nextInt();
			// 如果i小于0.5，那么加入到左结点,否则加入右结点
			/*
			 * if(i<0.5){ if(TreeNode.left==null){ TreeNode.left=new
			 * TreeNode(value); System.out.println("left--"+value); }else{
			 * //root结点的左子树已被创建的话，则以左结点为根节点创建
			 * System.out.println("root left--"+value);
			 * createBinaryTree(TreeNode.left, value); } }else{
			 * if(TreeNode.right==null){ TreeNode.right=new TreeNode(value);
			 * System.out.println("right--"+value); }else{ //若是在右子树中添加结点，则会调用该方法
			 * System.out.println("root right--"+value);
			 * createBinaryTree(TreeNode.right, value); } }
			 */
			// 如果小于的话加入到左边，大于加到右边(构造二叉排序树)
			if (value < node.val) {
				if (node.left == null) {
					node.left = new TreeNode(value);
					System.out.println("left--" + value);
				} else {
					// root结点的左子树已被创建的话，则以左结点为根节点创建
					System.out.println("root left--" + value);
					createBinaryTree(node.left, value);
				}
			} else {
				if (node.right == null) {
					node.right = new TreeNode(value);
					System.out.println("right--" + value);
				} else {
					// 若是在右子树中添加结点，则会调用该方法
					System.out.println("root right--" + value);
					createBinaryTree(node.right, value);
				}
			}
		}
	}

	// 前序遍历
	public static void preOrder(TreeNode root) {
		if (root != null) {
			System.out.print("TreeNode--" + root.val + "  ");
			preOrder(root.left);
			preOrder(root.right);
		}
	}
	//非递归前序遍历
	public static void preOrderNoRecursiv(TreeNode root){
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode node = root;
		while(node != null || !stack.isEmpty()){
			while(node != null){
				System.out.println(node.val);
				stack.push(node);
				node = node.left;
			}
			if(!stack.isEmpty()){
				node = stack.pop();
				node = node.right;
			}
		}
	}
	
	// 中序遍历
	public static void inOrder(TreeNode root) {
		if (root != null) {
			inOrder(root.left);
			System.out.print("node val :" + root.val + "  ");
			inOrder(root.right);
		}
	}

	public static void inOrderNoRecursiv(TreeNode root){
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode node = root;
		while(node != null || !stack.isEmpty()){
			while(node != null){
				stack.push(node);
				node = node.left;
			}
			if(!stack.isEmpty()){
				node = stack.pop();
				System.out.println(node.val);
				node = node.right;
			}
		}
	}
	// 要想通过两个遍历即得到树的结构，必须有中序遍历，也就是说前序和后序不能得到树的结构
	// 后序遍历
	public static void postOrder(TreeNode root) {
		if (root != null) {
			postOrder(root.left);
			postOrder(root.right);
			System.out.print("TreeNode--" + root.val + "  ");
		}
	}
	//后序遍历非递归实现是最难的，不能像前序或者中序那样。下面提供两种思路：
	
//	第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，
//	但是此时不能将其出栈并访问，因此其右孩子还未被访问。所以接下来按照相同的规则对其右子树进行相同的处理，
//	当访问完其右孩子时,该结点又出现在栈顶，此时可以将其出栈并访问。
//	这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶
//	只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。
	
//	第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，
//	因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，
//	但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，
//	这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
	
	public static void postOrderNoRecursiv(TreeNode root){
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur;                        //当前结点 
		TreeNode pre = null;                 //前一次访问的结点 
	    stack.push(root);
		while (!stack.empty()) {
			cur = stack.peek();
			//如果当前结点左右孩子都有的话
			//pre == cur.left || pre == cur.right 代表孩子结点已经被访问过
			if ((cur.left == null && cur.right == null)
					|| (pre != null && (pre == cur.left || pre == cur.right))) {
				System.out.println(cur.val); // 如果当前结点没有孩子结点或者孩子节点都已被访问过
				stack.pop();
				pre = cur;
			} else {
				//右孩子和左孩子依次入栈
				if (cur.right != null)
					stack.push(cur.right);
				if (cur.left != null)
					stack.push(cur.left);
			}
		}
	}
}
